/**
 * 641. 设计循环双端队列
 * https://leetcode-cn.com/problems/design-circular-deque/
 */
public class Solutions_641 {
    public static void main(String[] args) {
//        MyCircularDeque circularDeque = new MyCircularDeque(3);
//        boolean res1 = circularDeque.insertLast(1);  // output: true
//        System.out.println(res1);
//        boolean res2 = circularDeque.insertLast(2);	// output: true
//        System.out.println(res2);
//        boolean res3 = circularDeque.insertFront(3);	 // output: true
//        System.out.println(res3);
//        boolean res4 = circularDeque.insertFront(4);  // output: false
//        System.out.println(res4);
//        int res5 = circularDeque.getRear();  // output: 2
//        System.out.println(res5);
//        boolean res6 = circularDeque.isFull();  // output: true
//        System.out.println(res6);
//        boolean res7 = circularDeque.deleteLast();  // output: true
//        System.out.println(res7);
//        boolean res8 = circularDeque.insertFront(4);  // output: true
//        System.out.println(res8);
//        int res9 = circularDeque.getFront();  // output: 4
//        System.out.println(res9);

        MyCircularDeque circularDeque = new MyCircularDeque(3);
        boolean res1 = circularDeque.insertFront(9);  // output: true
        System.out.println(res1);
        int res2 = circularDeque.getRear();  // output: 9
        System.out.println(res2);
        boolean res3 = circularDeque.insertFront(9);  // output: true
        System.out.println(res3);
        int res4 = circularDeque.getRear();  // output: 9
        System.out.println(res4);
        boolean res5 = circularDeque.insertLast(5);	// output: true
        System.out.println(res5);  // 9 9 5
        int res6 = circularDeque.getFront();  // output: 9
        System.out.println(res6);
        int res7 = circularDeque.getRear();  // output: 5
        System.out.println(res7);
        boolean res8 = circularDeque.insertLast(8);	// output: false
        System.out.println(res8);
        boolean res9 = circularDeque.deleteLast();  // output: true
        System.out.println(res9);
        int res10 = circularDeque.getFront();  // output: 9
        System.out.println(res10);

//        MyCircularDeque circularDeque = new MyCircularDeque(8);
//        boolean res1 = circularDeque.insertFront(5);	 // output: true
//        System.out.println(res1);
//        int res2 = circularDeque.getFront();  // output: 5
//        System.out.println(res2);
//        boolean res3 = circularDeque.isEmpty();  // output: false
//        System.out.println(res3);
//        boolean res4 = circularDeque.deleteFront();  // output: true
//        System.out.println(res4);
//        boolean res5 = circularDeque.insertLast(3);	// output: true
//        System.out.println(res5);
//        int res6 = circularDeque.getRear();  // output: 3
//        System.out.println(res6);
//        boolean res7 = circularDeque.insertLast(7);  // output: false
//        System.out.println(res7);
    }
}

/**
 * 通过增加一个空闲索引位置，不论先进行 insertFront 操作，还是 insertLast 操作
 *      那么 head 指针总是指向 arr.length - 1，tail 指针总是指向 0
 * 那么取值索引已经确定
 *      - 队首元素：head 指针
 *      - 队尾元素：tail 指针 - 1
 *
 * 关键：tail 指针指向的永远是空的位置，要获取队尾元素时，tail - 1
 *      head 指针指向的是队首元素所在
 */
class MyCircularDeque {
    int[] arr;
    // 记录队首元素所在的位置
    int head;
    // 记录队尾元素所在的位置 + 1，为什么这样设置呢？
    // 1. 插入队尾元素时，直接在 tail 上插入，再做索引后移操作
    // 2. 可以先进行两个插入队首元素的操作，那么此时若通过 tail 来获取队尾元素，无法获取到，因为只修改了 head 指针
    //      那么可以通过 tail - 1 来获取队尾元素，因为 head 与 tail 是循环的
    //      队列元素 full 时，head 的前一指针就是 tail，tail 的后一指针就是 head
    int tail;
    int capacity;

    /** Initialize your data structure here. Set the size of the deque to be k. */
    public MyCircularDeque(int k) {
        capacity = k + 1;
        head = 0;
        tail = 0;
        arr = new int[capacity];
    }

    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        // 在 head 前插入一个元素
        -- head;
        if (head < 0) {
            head = arr.length - 1;
        }
//        head = (head - 1 + capacity) % capacity;
        arr[head] = value;
        return true;
    }

    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        // 先在 tail 索引上插入元素
        arr[tail] = value;
        // tail 索引后移
        if (++ tail == arr.length) {
            tail = 0;
        }
//        tail = (tail + 1) % capacity;
        return true;
    }

    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        // 不改变值，直接将 head 指针后移
        if (++ head == arr.length) {
            head = 0;
        }
//        head = (head + 1) % capacity;
        return true;
    }

    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        // 不改变值，直接将 tail 指针前移
        if (-- tail < 0) {
            tail = arr.length - 1;
        }
//        tail = (tail - 1 + capacity) % capacity;
        return true;
    }

    /** Get the front item from the deque. */
    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        // 直接获取队首元素
        return arr[head];
    }

    /** Get the last item from the deque. */
    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        // 获取队尾元素，需要取 tail - 1 索引上的元素
        return arr[(tail - 1 + capacity) % capacity];
    }

    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty() {
        // 容量是空的
        return head == tail;
    }

    /** Checks whether the circular deque is full or not. */
    public boolean isFull() {
        // 容量是满的
        return (tail + 1) % capacity == head;
    }
}
